/*
	XRegExp 0.2.5
	(c) 2007 Steven Levithan <http://stevenlevithan.com>
	MIT license

	Provides an augmented, cross-browser implementation of regular
	expressions, including support for additional flags.
*/


// Avoid name-space pollution and protect private variables through closure...
(function () {

/* Prevent this from running more than once, which would break references
to native globals. Implemented here rather than via an enclosing conditional
simply because having two enclosures around most of the codebase is ugly. */
if (window.XRegExp)
	return;

/*
	Copy various native globals for reference. The object is named
	``real`` since ``native`` is a reserved JavaScript keyword.
*/
var real = {
	RegExp:  RegExp,
	exec:    RegExp.prototype.exec,
	match:   String.prototype.match,
	replace: String.prototype.replace
};

/*
	Regex syntax parsing with support for the necessary cross-browser
	and context issues (escapings, character classes, etc.)

	Each of the regexes match any string entirely when applied repeatedly,
	hence the nested quantifiers have no risk of causing super-linear
	backtracking despite the lack of real or mimicked atomization.
*/
var re = {
	extended:            /(?:[^[#\s\\]+|\\(?:[\S\s]|$)|\[\^?]?(?:[^\\\]]+|\\(?:[\S\s]|$))*]?)+|(\s*#[^\n\r\u2028\u2029]*\s*|\s+)([?*+]|{[0-9]+(?:,[0-9]*)?})?/g,
	singleLine:          /(?:[^[\\.]+|\\(?:[\S\s]|$)|\[\^?]?(?:[^\\\]]+|\\(?:[\S\s]|$))*]?)+|\./g,
	characterClass:      /(?:[^\\[]+|\\(?:[\S\s]|$))+|\[\^?(]?)(?:[^\\\]]+|\\(?:[\S\s]|$))*]?/g,
	capturingGroup:      /(?:[^[(\\]+|\\(?:[\S\s]|$)|\[\^?]?(?:[^\\\]]+|\\(?:[\S\s]|$))*]?|\((?=\?))+|(\()(?:<([$\w]+)>)?/g,
	namedBackreference:  /(?:[^\\[]+|\\(?:[^k]|$)|\[\^?]?(?:[^\\\]]+|\\(?:[\S\s]|$))*]?|\\k(?!<[$\w]+>))+|\\k<([$\w]+)>([0-9]?)/g,
	replacementVariable: /(?:[^$]+|\$(?![1-9$&`']|{[$\w]+}))+|\$(?:([1-9]\d*|[$&`'])|{([$\w]+)})/g
};

/*** XRegExp
	Accepts a pattern and flags, returns a new, extended RegExp object.
	Differs from a native regex in that additional flags are supported
	and browser inconsistencies are ameliorated.

	 - ``x`` for free-spacing and comments
	 - ``s`` to cause dot to match all characters
	 - ``k`` to engage named capture
		- ``(<name>...)`` to capture with ``name``
		- ``\k<name>`` for a backreference to ``name`` inside the regex
		- ``${name}`` for a backreference to ``name`` inside a replacement string
		- backreferences stored in ``result.name`` or ``arguments[0].name``
*/
XRegExp = function (pattern, flags) {
	flags = flags || "";

	if (flags.indexOf("x") > -1) {
		pattern = real.replace.call(pattern, re.extended, function ($0, $1, $2) {
			// Keep backreferences separate from subsequent tokens unless the token is a quantifier
			return $1 ? ($2 || "(?:)") : $0;
		});
	}

	var hasNamedCapture = false;
	if (flags.indexOf("k") > -1) {
		var captureNames = [];
		pattern = real.replace.call(pattern, re.capturingGroup, function ($0, $1, $2) {
			if ($1) {
				if ($2) hasNamedCapture = true;
				captureNames.push($2 || null);
				return "(";
			} else {
				return $0;
			}
		});
		if (hasNamedCapture) {
			// Replace named with numbered backreferences
			pattern = real.replace.call(pattern, re.namedBackreference, function ($0, $1, $2) {
				var index = $1 ? captureNames.indexOf($1) : -1;
				// Keep backreferences separate from subsequent literal numbers
				return index > -1 ? "\\" + (index + 1) + ($2 ? "(?:)" + $2 : "") : $0;
			});
		}
	}

	/*
		If ] is the leading character in a character class, replace it with \] for consistent cross-
		browser handling. This is needed to maintain correctness without browser sniffing when
		constructing the regexes which deal with character classes. They treat a leading ] within a
		character class as a non-terminating, literal character, which is consistent with IE, Safari,
		Perl, PCRE, .NET, Python, Ruby, JGsoft, and most other regex flavors.
	*/
	pattern = real.replace.call(pattern, re.characterClass, function ($0, $1) {
		return $1 ? real.replace.call($0, "]", "\\]") : $0;
	});

	if (flags.indexOf("s") > -1) {
		pattern = real.replace.call(pattern, re.singleLine, function ($0) {
			return $0 === "." ? "[\\S\\s]" : $0;
		});
	}

	var regex = real.RegExp(pattern, real.replace.call(flags, /[sxk]+/g, ""));
	if (hasNamedCapture)
		regex._captureNames = captureNames;
	return regex;
};

/*
	Returns a new XRegExp object generated by recompiling the regex with the additional flags,
	which may include non-native flags. The original regex object is not altered.
*/
RegExp.prototype.addFlags = function (flags) {
	flags = (flags || "") + (this.global ? "g" : "") + (this.ignoreCase ? "i" : "") + (this.multiline ? "m" : "");
	var regex = new XRegExp(this.source, flags);
	// Preserve capture names if adding flags to a regex which has already had capture names attached
	if (!regex._captureNames && this._captureNames)
		regex._captureNames = this._captureNames.slice(0);
	return regex;
};

RegExp.prototype.exec = function (str) {
	var result = real.exec.call(this, str);
	if (!(this._captureNames && result && result.length > 1))
		return result;
	for (var i = 1; i < result.length; i++) {
		var name = this._captureNames[i - 1];
		if (name)
			result[name] = result[i];
	}
	return result;
};

String.prototype.match = function (regex) {
	if (!regex._captureNames || regex.global)
		return real.match.call(this, regex);
	// Run the overriden exec method
	return regex.exec(this);
};

String.prototype.replace = function (search, replacement) {
	// If search is not a regex which uses named capturing groups, use the native replace method
	if (!(search instanceof real.RegExp && search._captureNames))
		return real.replace.apply(this, arguments);

	if (typeof replacement === "function") {
		return real.replace.call(this, search, function () {
			// Convert arguments[0] from a string primitive to a String object which can store properties
			arguments[0] = new String(arguments[0]);
			// Store named backreferences on arguments[0] before calling replacement
			for (var i = 0; i < search._captureNames.length; i++) {
				if (search._captureNames[i])
					arguments[0][search._captureNames[i]] = arguments[i + 1];
			}
			/* The context object ``this`` is set to the global context ``window`` as it should be with stand-
			alone anonymous functions, although it's unlikely to be used within a replacement function. */
			return replacement.apply(window, arguments);
		});
	} else {
		return real.replace.call(this, search, function () {
			var args = arguments;
			return real.replace.call(replacement, re.replacementVariable, function ($0, $1, $2) {
				// Numbered backreference or special variable
				if ($1) {
					switch ($1) {
						case "$": return "$";
						case "&": return args[0];
						case "`": return args[args.length - 1].slice(0, args[args.length - 2]);
						case "'": return args[args.length - 1].slice(args[args.length - 2] + args[0].length);
						// Numbered backreference
						default:
							/* What does "$10" mean?
							 - Backreference 10, if 10 or more capturing groups exist
							 - Backreference 1 followed by "0", if 1-9 capturing groups exist
							 - Otherwise, it's the string "$10" */
							var literalNumbers = "";
							$1 = +$1; // Cheap type-conversion
							while ($1 > search._captureNames.length) {
								literalNumbers = $1.split("").pop() + literalNumbers;
								$1 = Math.floor($1 / 10); // Drop the last digit
							}
							return ($1 ? args[$1] : "$") + literalNumbers;
					}
				// Named backreference
				} else if ($2) {
					/* What does "${name}" mean?
					 - Backreference to named capture "name", if it exists
					 - Otherwise, it's the string "${name}" */
					var index = search._captureNames.indexOf($2);
					return index > -1 ? args[index + 1] : $0;
				} else {
					return $0;
				}
			});
		});
	}
};

})();
// ...End anonymous function

/*
	Accepts a pattern and flags, returns a new XRegExp object. If the regex has
	previously been cached, returns the cached copy, otherwise the new object is
	cached.
*/
XRegExp.cache = function (pattern, flags) {
	var key = "/" + pattern + "/" + (flags || "");
	return XRegExp.cache[key] || (XRegExp.cache[key] = new XRegExp(pattern, flags));
};

/*
	Overrides the global RegExp constructor/object with the XRegExp constructor.
	This precludes accessing the deprecated properties of the last match on the
	global RegExp object. It also changes the result of ``(/x/.constructor ==
	RegExp)`` and ``(/x/ instanceof RegExp)``, so use with caution.
*/
XRegExp.overrideNative = function () {
	RegExp = XRegExp;
};

if (!Array.prototype.indexOf) {
	// JavaScript 1.6 compliant indexOf from MooTools 1.11; MIT License
	Array.prototype.indexOf = function (item, from) {
		var len = this.length;
		for (var i = (from < 0) ? Math.max(0, len + from) : from || 0; i < len; i++) {
			if (this[i] === item)
				return i;
		}
		return -1;
	};
}
